package leetcode;

import java.util.*;

/*
   贪心算法
   一种在每一步选择中都采取当前状态下的最优选择（局部最优解），以期望通过局部最优解得到全局最优解的算法策略。贪心算法适用于某些问题，虽然不能保证对所有问题都能找到全局最优解，但对于特定问题是非常高效的
 */
public class LC_greedy {
    public static void main(String[] args) {
        LC_greedy lc = new LC_greedy();
        System.out.println(lc.canJump2(new int[]{2, 0, 0}));
        System.out.println(lc.canJump2(new int[]{2, 3, 1, 1, 4}));
        System.out.println(lc.jump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(lc.jump(new int[]{5,9,3,2,1,0,2,3,3,1,0,0}));
        System.out.println(lc.jump(new int[]{1, 2}));
        System.out.println(lc.jump(new int[]{1, 2, 3}));
        System.out.println(lc.jump(new int[]{2, 0, 0}));
    }
    /*
        LeetCode 121题
        给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
        返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     */
    public int maxProfit(int[] prices) {
        // 如果今天价格比历史最低价低，那么更新最低价格
        // 如果今天价格比最低价高，计算两天之间的差值，判断是否差值最大
        if (prices.length < 1) return 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            else max = Math.max(max, prices[i] - min);
        }
        return max;
    }
    /*
        LeetCode 55题
        给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
        判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     */
    public boolean canJump(int[] nums) {
        // 利用倒叙查看当前节点是否可以到达终点
        if(nums.length < 2) return true;
        int index = nums.length - 1;
        Set<Integer> set = new HashSet<>();
        set.add(index);
        for (int i = nums.length - 2; i >= 0; i--) {
            int temp = nums[i];
            if (temp >= index - i) set.add(i);
            else {
                for (int j = 1; j <= temp; j++) {
                    if (set.contains(i+j)) {
                        set.add(i);
                        break;
                    }
                }
            }
        }
        System.out.println(set);
        return set.contains(0);
    }
    public boolean canJump2(int[] nums) {
        // 查看当前坐标能够到达的最远点
        if(nums.length < 2) return true;
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            max = Math.max(max, i+nums[i]);
            // 当最远点为当前坐标，说明已经无法到达下一个坐标了
            if(max == i) return false;
        }
        return max >= nums.length - 1;
    }
    /*
        LeetCode 45题
        给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
        每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处
        返回到达 nums[n - 1] 的最小跳跃次数。
     */
    public int jump(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length - 1;) {
            int index = i + nums[i];
            for (int j = i+1; j <= index && j < nums.length - 1; j++) {
                if (j + nums[j] > i + nums[i]){
                    i = j;
                }
            }
            ans++;
            if (index >= nums.length - 1) return ans;
        }
        return ans;
    }
    /*
        给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
        注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
        返回一个表示每个字符串片段的长度的列表。
     */
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.toCharArray().length; i++) {
            map.put(s.charAt(i), i);
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length();) {
            char temp = s.charAt(i);
            end = map.get(temp);
            for (int j = i+1; j < end; j++) {
                Integer index = map.get(s.charAt(j));
                if (index > end) end = index;
            }
            ans.add(end - start + 1);
            i = start = end + 1;
        }
        return ans;
    }
}
